package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 **/
public class No011 {

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了28.26%的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了17.95%的用户
     */
    public int minArray(int[] numbers) {
        int length = numbers.length;

        if (numbers[0] < numbers[length - 1]) {
            // 还没有旋转
            return numbers[0];
        }

        int left;
        int right;
        for (int i = 0; i < length; i++) {
            left = i - 1 < 0 ? length - 1 : i - 1;
            right = i + 1 > length - 1 ? 0 : i + 1;

            if (numbers[i] < numbers[left] && numbers[i] <= numbers[right]) {
                return numbers[i];
            }
        }

        return numbers[0];
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.4 MB, 在所有 Java 提交中击败了19.07%的用户
     */
    public int minArray1(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        int mid = 0;

        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (numbers[mid] < numbers[right]) {
                right = mid;
            } else if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            } else {
                right--;
            }
        }

        return numbers[left];
    }
}
